class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        
        def backtracking(board):
            # 若有解，返回True；若无解，返回False
            for i in range(len(board)):
                for j in range(len(board)):
                    if board[i][j] != ".":
                        continue
                    for k in range(1, 10):
                        if is_valid(i, j, k, board):
                            board[i][j] = str(k)
                            if backtracking(board): return True 
                            board[i][j] = "."   # 回溯，撤销k
                    # 若数字1-9都不能成功填入空格，返回False无解
                    return False 
            return True
        
        # 判断行、列、9方格类是否冲突
        def is_valid(row, col, val, board):
            for i in range(9):
                if board[row][i] == str(val):
                    return False
            
            for j in range(9):
                if board[j][col] == str(val):
                    return False
            
            low_row, low_col = (row//3) * 3, (col // 3) * 3
            for i in range(low_row, low_row + 3):
                for j in range(low_col, low_col + 3):
                    if board[i][j] == str(val):
                        return False 
            return True
        
        backtracking(board)
# 方法二
class Solution:
    def solveSudoku(self, board: list[list[str]]) -> None:
        # 预处理行、列、子网格的已用数字
        self.rows = [[False]*10 for _ in range(9)]
        self.cols = [[False]*10 for _ in range(9)]
        self.boxes = [[[False]*10 for _ in range(3)] for _ in range(3)]
        self.spaces = []  # 存储所有空格坐标
        
        for i in range(9):
            for j in range(9):
                if board[i][j] != '.':
                    num = int(board[i][j])
                    self.rows[i][num] = True
                    self.cols[j][num] = True
                    self.boxes[i//3][j//3][num] = True
                else:
                    self.spaces.append((i, j))
        
        self.backtrack(board, 0)
    
    def backtrack(self, board: list[list[str]], idx: int) -> bool:
        if idx == len(self.spaces):
            return True  # 所有空格填满，找到解
        
        i, j = self.spaces[idx]
        
        # 生成候选数字并按升序排列（启发式优化）
        candidates = []
        for k in '123456789':
            num = int(k)
            if not (self.rows[i][num] or self.cols[j][num] or self.boxes[i//3][j//3][num]):
                candidates.append(k)
        
        # 尝试所有候选数字
        for k in candidates:
            num = int(k)
            # 更新预处理数据
            self.rows[i][num] = self.cols[j][num] = self.boxes[i//3][j//3][num] = True
            board[i][j] = k
            
            if self.backtrack(board, idx + 1):
                return True
            
            # 回溯操作
            self.rows[i][num] = self.cols[j][num] = self.boxes[i//3][j//3][num] = False
            board[i][j] = '.'
        
        return False